package solution.design;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-10-19 22:18
 * 单调栈
 */
public class MonotonicStack {


    /*===========================================================================================================================
    * 1.模板
    * 给你一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。
    * 这就是单调队列解决问题的模板。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。
    * while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了。
    * */
    public int[] nextGreaterElement(int[] nums){
        int n=nums.length;
        int[] res=new int[n];
        Stack<Integer> stack=new Stack<>();
        // 倒着往栈里放
        for (int i = n-1; i >=0 ; i--) {
            // 判定个子高矮
            while (!stack.isEmpty()&&stack.peek()<=nums[i]){
                stack.pop();
            }
            //nums[i]后的next great number
            res[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(nums[i]);
        }
        return res;
    }

    /*===========================================================================================================================
     * 739. 每日温度
     * 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
     * */
    public int[] dailyTemperatures(int[] temperatures) {
        int n=temperatures.length;
        int[] res=new int[n];
        Stack<Integer> stack=new Stack<>();
        // 倒着往栈里放
        for (int i = n-1; i >=0 ; i--) {
            // 判定个子高矮
            while (!stack.isEmpty()&&temperatures[stack.peek()]<=temperatures[i]){
                stack.pop();
            }
            // 将索引入栈，而不是元素,得到索引间距
            res[i]=stack.isEmpty()?0:(stack.peek()-i);
            stack.push(i);
        }
        return res;
    }


    /*===========================================================================================================================
     * 496. 下一个更大元素 I
     * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
     * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
     * */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n=nums1.length,m=nums2.length;
        int[] next=new int[m];
        int[] res=new int[n];
        Stack<Integer> stack=new Stack<>();
        // 倒着往栈里放
        for (int i = m-1; i >=0 ; i--) {
            // 判定个子高矮
            while (!stack.isEmpty()&&stack.peek()<=nums2[i]){
                stack.pop();
            }
            //nums[i]后的next great number
            next[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(nums2[i]);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nums1[i]==nums2[j]){
                    res[i]=next[j];
                }
            }
        }
        return res;
    }



    /*===========================================================================================================================
     * 503. 下一个更大元素 II
     * 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。
     * 数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
     * 常用套路就是将数组长度翻倍：利用循环数组的技巧来模拟数组长度翻倍的效果。
     * */
    public int[] nextGreaterElements(int[] nums) {
        int n=nums.length;
        int[] res=new int[n];
        Stack<Integer> stack=new Stack<>();
        // 假装这个数组长度翻倍了
        for (int i = 2*n-1; i >=0; i--) {
            // 索引要求模，其他的和模板一样
            while (!stack.isEmpty()&&stack.peek()<=nums[i%n])
                stack.pop();
            res[i%n]=stack.isEmpty()?-1:stack.peek();
            stack.push(nums[i%n]);
        }
        return res;
    }

}
